package org.example.myleet.bfs;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.Parser;
import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class BfsSolution {

    //p3
    public int lengthOfLongestSubstring(String s) {
        int i = 0, max = 0;
        Stack<Set<Character>> thisRound = new Stack<>();
        Stack<Set<Character>> nextRound = new Stack<>();
        while (i < s.length()) {
            char c = s.charAt(i);
            if (thisRound.isEmpty()) {
                max = 1;
            } else {
                while (!thisRound.isEmpty()) {
                    //检查的每个缓存的子串
                    Set<Character> charSet = thisRound.pop();
                    if (charSet.contains(c)) {
                        //如果已经包含有相应的字母，即不重复的子串已经到达最长，取新的最长
                        max = Math.max(max, charSet.size());
                    } else {
                        //继续延长子串，并放到下一次检查的缓存子串中
                        charSet.add(c);
                        nextRound.push(charSet);
                    }
                }
                //交换已经清空的缓存区
                Stack<Set<Character>> tmp = thisRound;
                thisRound = nextRound;
                nextRound = tmp;
            }
            Set<Character> charSet = new HashSet<>();
            charSet.add(c);
            thisRound.push(charSet);
            ++i;
        }
        while (!thisRound.isEmpty()) {
            //如果还有未检查的子串都检查一遍
            Set<Character> charSet = thisRound.pop();
            max = Math.max(max, charSet.size());
        }
        return max;
    }

    /**
     * 102【BFS】二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (null == root) return answer;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> values = new ArrayList<>(n);
            for (int i = 0; i < n; ++i) {
                TreeNode node = queue.poll();
                values.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            answer.add(values);
        }
        return answer;
    }

    /**
     * 106【BFS】从中序与后序遍历序列构造二叉树
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 1) return new TreeNode(postorder[0]);
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        Queue<int[]> inRangeQueue = new LinkedList<>();
        inRangeQueue.offer(new int[]{0, inorder.length - 1});
        Queue<int[]> postRangeQueue = new LinkedList<>();
        postRangeQueue.offer(new int[]{0, postorder.length - 1});
        while (!nodeQueue.isEmpty()) {
            int n = nodeQueue.size();
            for (int x = 0; x < n; ++x) {
                TreeNode parent = nodeQueue.poll();
                int[] inRange = inRangeQueue.poll();
                int[] postRange = postRangeQueue.poll();
                int parentVal = parent.val;
                int i = inRange[0], cnt = 0;
                while (parentVal != inorder[i]) {
                    ++i;
                    ++cnt;
                }
                int[] leftInRange = new int[]{inRange[0], i - 1};
                int[] leftPostRange = new int[]{postRange[0], postRange[0] + cnt - 1};
                if (leftPostRange[0] == leftPostRange[1]) {
                    parent.left = new TreeNode(postorder[leftPostRange[0]]);
                } else if (leftPostRange[0] < leftPostRange[1]) {
                    parent.left = new TreeNode(postorder[leftPostRange[1]]);
                    nodeQueue.offer(parent.left);
                    inRangeQueue.offer(leftInRange);
                    postRangeQueue.offer(leftPostRange);
                }
                int[] rightInRange = new int[]{i + 1, inRange[1]};
                int[] rightPostRange = new int[]{postRange[0] + cnt, postRange[1] - 1};
                if (rightPostRange[0] == rightPostRange[1]) {
                    parent.right = new TreeNode(postorder[rightPostRange[0]]);
                } else if (rightPostRange[0] < rightPostRange[1]) {
                    parent.right = new TreeNode(postorder[rightPostRange[1]]);
                    nodeQueue.offer(parent.right);
                    inRangeQueue.offer(rightInRange);
                    postRangeQueue.offer(rightPostRange);
                }
            }
        }
        return root;
    }

    /**
     * 297【BFS】二叉树的序列化与反序列化
     * 二叉树的序列化与反序列化
     * 广度优先搜索，序列化时对同层级的节点进行遍历，反序列化时按照层级重建二叉树
     */
    static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (Objects.isNull(root)) {
                return "[]";
            }
            //队列保存待遍历的同层级的节点
            Queue<TreeNode> queue = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            sb.append(root.val);
            sb.append(",");
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode parent = queue.poll();
                if (Objects.isNull(parent.left)) {
                    //下一层没有左子节点，接null，并且不会有下一层的节点进入队列
                    sb.append("null");
                } else {
                    //下一层有左子节点，左子节点加入队列
                    sb.append(parent.left.val);
                    queue.offer(parent.left);
                }
                sb.append(",");
                if (Objects.isNull(parent.right)) {
                    sb.append("null");
                } else {
                    sb.append(parent.right.val);
                    queue.offer(parent.right);
                }
                sb.append(",");
            }
            //最后对结果进行修饰，移除结尾所有"null,"
            String suffix = sb.substring(sb.length() - 5, sb.length());
            while ("null,".equals(suffix)) {
                sb.delete(sb.length() - 5, sb.length());
                if (sb.length() >= 5) {
                    suffix = sb.substring(sb.length() - 5, sb.length());
                } else {
                    break;
                }
            }
            //移除最后一个","
            sb.deleteCharAt(sb.length() - 1);
            return "[" + sb.toString() + "]";
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            data = data.substring(1, data.length() - 1);
            //分割出所有节点值字符串
            String[] nodeValues = data.split(",");
            if (nodeValues.length == 0) {
                return null;
            }
            Integer rootValue = parseNodeValue(nodeValues[0]);
            if (Objects.isNull(rootValue)) {
                return null;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(rootValue);
            queue.offer(root);
            //读取游标
            int readIdx = 1;
            while (!queue.isEmpty()) {
                TreeNode parent = queue.poll();
                if (readIdx < nodeValues.length) {
                    String leftNodeValue = nodeValues[readIdx++];
                    Integer leftNodeVal = parseNodeValue(leftNodeValue);
                    if (Objects.isNull(leftNodeVal)) {
                        //节点为空，没有下一层级的子节点
                        parent.left = null;
                    } else {
                        //节点不为空，下一层级的子节点加入到队列中
                        parent.left = new TreeNode(leftNodeVal);
                        queue.offer(parent.left);
                    }
                }
                if (readIdx < nodeValues.length) {
                    String rightNodeValue = nodeValues[readIdx++];
                    Integer rightNodeVal = parseNodeValue(rightNodeValue);
                    if (Objects.isNull(rightNodeVal)) {
                        parent.right = null;
                    } else {
                        parent.right = new TreeNode(rightNodeVal);
                        queue.offer(parent.right);
                    }
                }
            }
            return root;
        }

        private Integer parseNodeValue(String s) {
            if ("null".equals(s) || s.length() == 0) {
                return null;
            }
            return Integer.valueOf(s);
        }
    }

    /**
     * {i, j}的变化
     */
    private static final int[][] DIRECTIONS4 = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    //p1129
    static class Status1129 {
        int node;
        int step;
        boolean prevRed;

        public Status1129(int node, int step, boolean prevRed) {
            this.node = node;
            this.step = step;
            this.prevRed = prevRed;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Status1129 that = (Status1129) o;
            return node == that.node && step == that.step && prevRed == that.prevRed;
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, step, prevRed);
        }
    }
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        answer[0] = 0;
        //记录某一点是否曾经从红色边过来
        boolean[] visitedRed = new boolean[n];
        //记录某一点是否曾经从蓝色边过来
        boolean[] visitedBlue = new boolean[n];
        //出发状态
        Set<Status1129> startStatus = new HashSet<>();
        //BFS所使用的队列
        Queue<Status1129> queue = new LinkedList<>();
        //红色边的快速映射，方便查找
        Set<Integer>[] redEdgeMap = new Set[n];
        for (int[] edge : redEdges) {
            Set<Integer> nodes = redEdgeMap[edge[0]];
            if (null == nodes) {
                nodes = new HashSet<>();
            }
            nodes.add(edge[1]);
            redEdgeMap[edge[0]] = nodes;
            if (edge[0] == 0) {
                //从0指向某一点，所以edge[1]属于开始状态，添加到开始状态集合中，注意是从红色边到达edge[1]点的
                Status1129 startState = new Status1129(edge[1], 1, true);
                startStatus.add(startState);
            }
        }
        //蓝色边的快速映射，方便查找
        Set<Integer>[] blueEdgeMap = new Set[n];
        for (int[] edge : blueEdges) {
            Set<Integer> nodes = blueEdgeMap[edge[0]];
            if (null == nodes) {
                nodes = new HashSet<>();
            }
            nodes.add(edge[1]);
            blueEdgeMap[edge[0]] = nodes;
            if (edge[0] == 0) {
                Status1129 startState = new Status1129(edge[1], 1, false);
                startStatus.add(startState);
            }
        }
        for (Status1129 status : startStatus) {
            //BFS起始状态
            queue.offer(status);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                //弹出一个点
                Status1129 status = queue.poll();
                //这个状态如果是从红色边过来的，就记录曾经从红色边过来，否则就是从蓝色边过来
                boolean[] visited = status.prevRed ? visitedRed : visitedBlue;
                visited[status.node] = true;
                if (answer[status.node] < 0) {
                    //如果从来未到达过此点，则记录到达这个点的最短路径
                    answer[status.node] = status.step;
                }
                //这个状态如果是从红色边过来的，下一条能走的边是蓝色的，否则下一条能走的边是红色的
                Set<Integer>[] edgeMap = status.prevRed ? blueEdgeMap : redEdgeMap;
                Set<Integer> nextNodes = edgeMap[status.node];
                if (null != nextNodes) {
                    for (int nextNode : nextNodes) {
                        if ((!visitedRed[nextNode] && !status.prevRed) || (!visitedBlue[nextNode] && status.prevRed)) {
                            //两种情况可以继续传播
                            //一是从红色边到达status.node，若nextNode还未走status.node->nextNode的蓝色边，则可以继续走，step + 1，颜色反转
                            //二是从蓝色边到达status.node，若nextNode还未走status.node->nextNode的红色边，则可以继续走，step + 1，颜色反转
                            Status1129 nextStatus = new Status1129(nextNode, status.step + 1, !status.prevRed);
                            queue.offer(nextStatus);
                        }
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 103【BFS】二叉树的锯齿形层序遍历
     * 1 ms
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (null == root) {
            return new LinkedList<>();
        }
        List<List<Integer>> result = new LinkedList<>();
        //锯齿状遍历，代表当前层级是自左至右还是自右至左
        boolean L2R = true;
        //BFS辅助数组，当前待遍历的节点
        Queue<TreeNode> list = new LinkedList<>();
        //初始化，根节点先遍历
        list.add(root);
        while (!list.isEmpty()) {
            //当前层级的遍历结果
            List<Integer> l = new LinkedList<>();
            //限制只推出当前层节点
            int len = list.size();
            for (int i=0; i<len; i++) {
                TreeNode n = list.poll();
                if (null == n) {
                    break;
                }
                //遍历当前层级的节点
                if (L2R) {
                    //当前层级自左至右，即顺着追加在结果末尾
                    l.add(n.val);
                } else {
                    //当前层级自右至左，即节点值一直插入在列表头
                    l.add(0, n.val);
                }
                //观察左右子节点是否不为空，不为空则放入待遍历的节点中等下一层遍历
                if (null != n.left) {
                    list.offer(n.left);
                }
                if (null != n.right) {
                    list.offer(n.right);
                }
            }
            if (!l.isEmpty()) {
                //当前层级不为空，加入到结果中
                result.add(l);
            }
            //锯齿状遍历，左右方向交换
            L2R = !L2R;
        }
        return result;
    }


    /**
     * 116【BFS】填充每个节点的下一个右侧节点指针
     */
    class Node116 {
        public int val;
        public Node116 left;
        public Node116 right;
        public Node116 next;

        public Node116() {}

        public Node116(int _val) {
            val = _val;
        }

        public Node116(int _val, Node116 _left, Node116 _right, Node116 _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
    public Node116 connect(Node116 root) {
        if (root == null) {
            return null;
        }
        Queue<Node116> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Queue<Node116> t = new LinkedList<>();
            int len = queue.size();
            Node116 cur = queue.poll();
            for (int i = 0; i < len; ++i) {
                if (cur.left != null) {
                    t.offer(cur.left);
                }
                if (cur.right != null) {
                    t.offer(cur.right);
                }
                cur.next = queue.poll();
                cur = cur.next;
                if (cur == null) break;
            }
            while (!t.isEmpty()) {
                queue.offer(t.poll());
            }
        }
        return root;
    }

    /**
     * 127【BFS】单词接龙
     * 单向BFS解题
     * 此题满足BFS的几个特征：
     * 在有限的空间中查找
     * 不会重复查找已经访问过的位置
     * 下一步变化依赖上一步状态，下一步由上一步通过一种规则转换
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //做成set用来检查endWord是否存在
        Set<String> wordDict = new HashSet<>(wordList.size());
        //未访问过的位置，即可访问位置
        Set<Integer> availablePosSet = new HashSet<>(wordList.size());
        for (int i=0; i<wordList.size(); i++) {
            wordDict.add(wordList.get(i));
            availablePosSet.add(i);
        }
        if (!wordDict.contains(endWord)) {
            //endWord不在字典中，退出
            return 0;
        }
        boolean found = false;
        //记录转换步骤数
        int step = 0;
        //BFS中下一回合等待访问的单词
        Stack<String> waitWords = new Stack<>();
        //BFS中当前回合将要访问的单词
        Stack<String> visitWords = new Stack<>();
        //初始化，压入第一个需要访问的单词，就是beginWord
        waitWords.push(beginWord);
        breakTag:
        while (!waitWords.isEmpty()) {
            //回合数+1
            ++step;
            //进入本回合，交换数据，开始本回合的搜索
            Stack<String> temp = visitWords;
            visitWords = waitWords;
            waitWords = temp;
            while (!visitWords.isEmpty()) {
                //弹出需要访问的单词
                String visitWord = visitWords.pop();
                if (visitWord.equalsIgnoreCase(endWord)) {
                    //候选单词中找到endWord，退出得答案
                    found = true;
                    break breakTag;
                }
                //记录访问过的位置，本回合搜索完后将标记成已经访问过（移除掉），后续不再访问
                Set<Integer> removeSet = new HashSet<>();
                for (int p : availablePosSet) {
                    String transWord = wordList.get(p);
                    boolean canBeTransformed = false;
                    boolean finished = false;
                    //要求有且只有改变一个字母的单词才是下一个状态
                    int diff = 0;
                    for (int i = 0; i< visitWord.length(); i++) {
                        if (visitWord.charAt(i) != transWord.charAt(i)) {
                            if (diff < 1) {
                                ++diff;
                            } else {
                                finished = true;
                                break;
                            }
                        }
                    }
                    if (!finished) {
                        if (diff == 1) {
                            canBeTransformed = true;
                        }
                    }
                    if (canBeTransformed) {
                        //检查未访问过的单词transWord
                        //如果此单词与visitWord仅差一个字母，说明transWord可以由visitWord变换过来
                        //transWord加入到待访问的集合中，并且这个位置标记成已经访问过（移除掉）
                        waitWords.push(transWord);
                        removeSet.add(p);
                    }
                }
                //将访问过的位置标记成已经访问过（移除掉）
                availablePosSet.removeAll(removeSet);
            }
        }
        if (found) {
            return step;
        }
        return 0;
    }

    /**
     * 322【BFS】零钱兑换
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        boolean[] visited = new boolean[amount + 1];
        int step = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(amount);
        visited[amount] = true;
        while (!queue.isEmpty()) {
            ++step;
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                Integer remain = queue.poll();
                for (int coin : coins) {
                    int nextRemain = remain - coin;
                    if (nextRemain >= 0 && !visited[nextRemain]) {
                        if (nextRemain == 0) return step;
                        queue.offer(nextRemain);
                        visited[nextRemain] = true;
                    }
                }
            }
        }
        return -1;
    }

    /**
     * 514【BFS + DP】自由之路
     */
    public int findRotateSteps(String ring, String key) {
        char[] keyCharArr = key.toCharArray(), ringCharArr = ring.toCharArray();
        int l = key.length(), n = ring.length();
        //记录输入第i个字符时轮盘转到j位置需要操作的次数，初始化无穷大（MAX）
        int[][] dp = new int[l + 1][n];
        for (int i = 0; i <= l; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        //BFS队列
        Queue<int[]> queue = new LinkedList<>();
        //第一步是初始状态，待匹配位置0，轮盘位置0，操作数0
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int[] state = queue.poll();
                int k = state[0]; //待匹配位置
                int r = state[1]; //轮盘位置
                int op = state[2]; //操作数
                if (dp[k][r] < Integer.MAX_VALUE) continue; //不是MAX值说明能够以更少操作数到达这个状态，剪枝
                dp[k][r] = op; //可以到达当前状态的最少操作数
                if (k >= l) continue; //完成匹配的状态，剪枝
                char kc = keyCharArr[k];
                char rc = ringCharArr[r];
                if (kc == rc) {
                    //能够匹配上，那么输入这个字母一定是最优操作，待匹配位置+1，轮盘位置不变，操作数+1
                    queue.offer(new int[]{k + 1, r, op + 1});
                } else {
                    //未能匹配上，则向左或向右转动轮盘，待匹配位置不变，轮盘位置-1或+1，操作数+1
                    queue.offer(new int[]{k, (r + 1) % n, op + 1});
                    queue.offer(new int[]{k, (r - 1 + n) % n, op + 1});
                }
            }
        }
        //待匹配位置为l的结果中挑最小的步数即可
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            answer = Math.min(answer, dp[l][i]);
        }
        return answer;
    }

    /**
     * 993【BFS】二叉树的堂兄弟节点
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            boolean flagX = false, flagY = false;
            for (int i = 0; i < n; ++i) {
                TreeNode node = queue.poll();
                //是否已经找到其中一个，如果两个都没找到就是false
                boolean findOne = flagX || flagY;
                if (null != node.left) {
                    if (node.left.val == x) flagX = true;
                    if (node.left.val == y) flagY = true;
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    if (node.right.val == x) flagX = true;
                    if (node.right.val == y) flagY = true;
                    queue.offer(node.right);
                }
                if (!findOne) {
                    //如果两个都找到，并且是在node节点下，则为兄弟节点，不是堂兄弟节点，返回false
                    if (flagX && flagY) return false;
                } else {
                    //如果是原来只找到一个，然后在同一层的另一个父节点上找到另一个，则符合题意返回true
                    if (flagX && flagY) return true;
                }
            }
            //如果同一层只找到一个，则x、y肯定不是堂兄弟节点，返回false
            if (flagX || flagY) return false;
        }
        //找不齐两个节点，默认返回false
        return false;
    }

    //p1210
    public int minimumMoves(int[][] grid) {
        int[][] DIRECTIONS = new int[][]{{0, 1}, {1, 0}};
        int H = 0, V = 1, n = grid.length;
        //每个位置都可能有横向和纵向两种状态，两种都记录是否被访问过
        boolean[][][] visited = new boolean[n][n][2];
        visited[0][0][H] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, H, 0});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int[] s = queue.poll();
                if (s[0] == n - 1 && s[1] == n - 2 && s[2] == H) {
                    //到达终点
                    return s[3];
                }
                if (s[2] == H) {
                    for (int[] direction : DIRECTIONS) {
                        int r = s[0] + direction[0];
                        int c = s[1] + direction[1];
                        if (0 <= r && r < n && 0 <= c && c < n && grid[r][c] == 0 && c + 1 < n && grid[r][c + 1] == 0 && !visited[r][c][H]) {
                            //可以向右或向下移动
                            queue.offer(new int[]{r, c, H, s[3] + 1});
                            visited[r][c][H] = true;
                        }
                    }
                    if (s[0] < n - 1 && s[1] < n - 1 && grid[s[0] + 1][s[1]] == 0 && grid[s[0] + 1][s[1] + 1] == 0 && !visited[s[0]][s[1]][V]) {
                        //可以从横向变成纵向
                        queue.offer(new int[]{s[0], s[1], V, s[3] + 1});
                        visited[s[0]][s[1]][V] = true;
                    }
                } else {
                    for (int[] direction : DIRECTIONS) {
                        int r = s[0] + direction[0];
                        int c = s[1] + direction[1];
                        if (0 <= r && r < n && 0 <= c && c < n && grid[r][c] == 0 && r + 1 < n && grid[r + 1][c] == 0 && !visited[r][c][V]) {
                            //可以向右或向下移动
                            queue.offer(new int[]{r, c, V, s[3] + 1});
                            visited[r][c][V] = true;
                        }
                    }
                    if (s[0] < n - 1 && s[1] < n - 1 && grid[s[0]][s[1] + 1] == 0 && grid[s[0] + 1][s[1] + 1] == 0 && !visited[s[0]][s[1]][H]) {
                        //可以从纵向变成横向
                        queue.offer(new int[]{s[0], s[1], H, s[3] + 1});
                        visited[s[0]][s[1]][H] = true;
                    }
                }
            }
        }
        return -1;
    }

    //1267【BFS】统计参与通信的服务器
    public int countServers(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int answer = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int batchCnt = 0;
                Queue<int[]> queue = new LinkedList<>();
                if ((!visited[i][j]) && grid[i][j] == 1) {
                    visited[i][j] = true;
                    queue.offer(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int s = queue.size();
                        for (int x = 0; x < s; ++x) {
                            int[] p = queue.poll();
                            int r = p[0], c = p[1];
                            ++batchCnt;
                            //向左探索
                            for (int k = c + 1; k < n; ++k) {
                                if ((!visited[r][k]) && grid[r][k] == 1) {
                                    visited[r][k] = true;
                                    queue.offer(new int[]{r, k});
                                }
                            }
                            //向右探索
                            for (int k = c - 1; k >= 0; --k) {
                                if ((!visited[r][k]) && grid[r][k] == 1) {
                                    visited[r][k] = true;
                                    queue.offer(new int[]{r, k});
                                }
                            }
                            //向下探索
                            for (int k = r + 1; k < m; ++k) {
                                if ((!visited[k][c]) && grid[k][c] == 1) {
                                    visited[k][c] = true;
                                    queue.offer(new int[]{k, c});
                                }
                            }
                            //向上探索
                            for (int k = r - 1; k >= 0; --k) {
                                if ((!visited[k][c]) && grid[k][c] == 1) {
                                    visited[k][c] = true;
                                    queue.offer(new int[]{k, c});
                                }
                            }
                        }
                    }
                }
                if (batchCnt > 1) answer += batchCnt;
            }
        }
        return answer;
    }

    /**
     * 1466【BFS】重新规划路线
     * 官方解用DFS更快，更剩空间，记录存在的路径为1，不存在的路径为0，从0节点开始DFS，路过的路径都加上权重即为答案
     */
    public int minReorder(int n, int[][] connections) {
        Set<Integer>[] capableDest = new Set[n];
        Set<Integer>[] adjMat = new Set[n];
        for (int[] conn : connections) {
            Set<Integer> dest = capableDest[conn[0]];
            if (null == dest) dest = new HashSet<>();
            dest.add(conn[1]);
            capableDest[conn[0]] = dest;
            Set<Integer> adj = adjMat[conn[0]];
            if (null == adj) adj = new HashSet<>();
            adj.add(conn[1]);
            adjMat[conn[0]] = adj;
            adj = adjMat[conn[1]];
            if (null == adj) adj = new HashSet<>();
            adj.add(conn[0]);
            adjMat[conn[1]] = adj;
        }
        int answer = 0;
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited[0] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int city = q.poll();
                Set<Integer> adj = adjMat[city];
                if (null != adj) {
                    for (Integer neighbour : adj) {
                        if (!visited[neighbour]) {
                            Set<Integer> dest = capableDest[neighbour];
                            if (null == dest || !dest.contains(city)) ++answer;
                            q.offer(neighbour);
                            visited[neighbour] = true;
                        }
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 1654【BFS】到家的最少跳跃次数
     */
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        //因为只能往回跳1次，那么最远只能到达x + b的位置，超过这个位置则不可能回得来
        int maxForbid = 0;
        HashSet<Integer> forbiddenP = new HashSet<>();
        for (int forbid : forbidden) {
            forbiddenP.add(forbid);
            maxForbid = Math.max(maxForbid, forbid);
        }
        int rightBound = x + b;
        if (a < b) rightBound = Math.max(maxForbid + a + b, x);
        HashMap<Integer, boolean[]> visited = new HashMap<>();
        //0应该被认为已经前进到达过或者是后退到达过，反正不能重新到达0位置，否则没有意义
        visited.put(0, new boolean[]{true, true});
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 1});
        int step = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                int[] p = queue.poll();
                if (p[0] == x) {
                    return step;
                }
                int pF = p[0] + a;
                if (!forbiddenP.contains(pF) && pF <= rightBound) {
                    if (visited.containsKey(pF)) {
                        boolean[] status = visited.get(pF);
                        if (!status[0]) {
                            status[0] = true;
                            visited.put(pF, status);
                            queue.offer(new int[]{pF, 0});
                        }
                    } else {
                        visited.put(pF, new boolean[]{true, false});
                        queue.offer(new int[]{pF, 0});
                    }
                }
                if (p[1] > 0) continue;
                int pB = p[0] - b;
                if (pB <= 0 || forbiddenP.contains(pB)) continue;
                if (visited.containsKey(pB)) {
                    boolean[] status = visited.get(pB);
                    if (!status[1]) {
                        status[1] = true;
                        visited.put(pB, status);
                        queue.offer(new int[]{pB, 1});
                    }
                } else {
                    visited.put(pB, new boolean[]{false, true});
                    queue.offer(new int[]{pB, 1});
                }
            }
            ++step;
        }
        return -1;
    }

    //p1765
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] map = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isWater[i][j] == 1) {
                    map[i][j] = 0;
                    visited[i][j] = true;
                    //遇到水域，则周边位置入队列
                    for (int k = 0; k < 4; ++k) {
                        int i_ = DIRECTIONS4[k][0] + i;
                        int j_ = DIRECTIONS4[k][1] + j;
                        if (0 <= i_ && i_ < m && 0 <= j_ && j_ < n && !visited[i_][j_]) {
                            queue.offer(new int[]{i_, j_});
                            visited[i_][j_] = true;
                        }
                    }
                } else {
                    map[i][j] = 10000;
                }
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int x = 0; x < size; ++x) {
                int[] position = queue.poll();
                int i = position[0];
                int j = position[1];
                //取周边已经遍历过的位置的最低值+1作为该位置的高度
                for (int k = 0; k < 4; ++k) {
                    int i_ = DIRECTIONS4[k][0] + i;
                    int j_ = DIRECTIONS4[k][1] + j;
                    if (0 <= i_ && i_ < m && 0 <= j_ && j_ < n) {
                        if (visited[i_][j_]) {
                            map[i][j] = Math.min(map[i][j], map[i_][j_] + 1);
                        } else {
                            queue.offer(new int[]{i_, j_});
                            visited[i_][j_] = true;
                        }
                    }
                }
            }
        }
        return map;
    }

    /**
     * 1993【BFS】树上的操作
     */
    static class LockingTree {
        static class Node {
            int parent;
            Set<Integer> children;
            boolean locked;
            Integer userId;
            public Node(int parent) {
                this.parent = parent;
                children = new HashSet<>();
                locked = false;
                userId = -1;
            }
        }

        private Node[] tree;

        public LockingTree(int[] parent) {
            int n = parent.length;
            tree = new Node[n];
            for (int i = 0; i < n; ++i) {
                int p = parent[i];
                if (tree[i] == null) {
                    tree[i] = new Node(p);
                }
                tree[i].parent = p;
                if (p > -1) {
                    if (tree[p] == null) {
                        tree[p] = new Node(-1);
                    }
                    Node pa = tree[p];
                    pa.children.add(i);
                }
            }
        }

        public boolean lock(int num, int user) {
            Node node = tree[num];
            if (node.locked) return false;
            node.locked = true;
            node.userId = user;
            return true;
        }

        public boolean unlock(int num, int user) {
            Node node = tree[num];
            if (!node.locked || node.userId != user) return false;
            node.locked = false;
            node.userId = -1;
            return true;
        }

        public boolean upgrade(int num, int user) {
            Node cur = tree[num];
            if (cur.locked) return false;
            if (cur.parent > -1) {
                //检查指定结点有没有上锁的祖先结点
                Node pa = tree[cur.parent];
                if (pa.locked) return false;
                boolean ancensterLocked = false;
                while (pa.parent > -1) {
                    if (pa.locked) {
                        ancensterLocked = true;
                        break;
                    }
                    pa = tree[pa.parent];
                }
                if (pa.locked) return false;
                if (ancensterLocked) return false;
            }
            //解锁所有锁定状态的子孙结点，如果没有锁定状态的子孙结点，返回失败
            boolean lockedDescendant = false;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(num);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; ++i) {
                    Node descendant = tree[queue.poll()];
                    if (descendant.locked) {
                        lockedDescendant = true;
                        descendant.locked = false;
                        descendant.userId = -1;
                    }
                    for (int child : descendant.children) {
                        queue.offer(child);
                    }
                }
            }
            if (lockedDescendant) {
                cur.locked = true;
                cur.userId = user;
            }
            return lockedDescendant;
        }
    }

    //p2039
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        Node2039[] node2039s = new Node2039[n];
        //建图（相互引用的多叉树）
        for (int[] edge : edges) {
            if (null == node2039s[edge[0]]) {
                node2039s[edge[0]] = new Node2039(edge[0]);
            }
            if (null == node2039s[edge[1]]) {
                node2039s[edge[1]] = new Node2039(edge[1]);
            }
            node2039s[edge[0]].addChild(node2039s[edge[1]]);
            node2039s[edge[1]].addChild(node2039s[edge[0]]);
        }
        //BFS计算所有节点距离0节点的最短距离
        boolean[] visited = new boolean[n];
        Queue<Node2039> queue = new LinkedList<>();
        int[] distances = new int[n];
        queue.offer(node2039s[0]);
        int distance = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                Node2039 node2039 = queue.poll();
                visited[node2039.val] = true;
                if (0 == distances[node2039.val]) {
                    distances[node2039.val] = distance;
                }
                for (Node2039 child : node2039.children) {
                    if (!visited[child.val]) {
                        queue.offer(child);
                    }
                }
            }
            ++distance;
        }
        int maxBusyTime = 0;
        for (int i = 1; i < n; ++i) {
            //X节点发出的信息到根节点处理后再返回到X节点的总距离
            int totalDistance = distances[i] * 2;
            //X节点需要发出的信息总数 = 第一个发出的信息 + 总距离/patience[i]
            //特别地，当总距离 == patience[i]时，可以减少一个信息的发出，因为收到回信马上停止发送重复信息
            int totalMsgCount = 1 + totalDistance / patience[i];
            if (totalDistance % patience[i] == 0) {
                --totalMsgCount;
            }
            //X节点总的所需信息传输繁忙时间，(totalMsgCount - 1)为重复信息的数量
            int serverBusyTime = totalDistance + (totalMsgCount - 1) * patience[i];
            if (maxBusyTime < serverBusyTime) {
                maxBusyTime = serverBusyTime;
            }
        }
        return maxBusyTime + 1;
    }

    static class Node2039 {
        int val;
        List<Node2039> children;

        public Node2039(int val) {
            this.val = val;
            children = new ArrayList<>();
        }

        public void addChild(Node2039 child) {
            children.add(child);
        }
    }

    //p2045
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        //节点访问次数记录，需要注意，如果一个节点可能被访问到第3次时，那么这个节点一定不在次短路径上
        //推理可以知道次短路径只有两种可能，要么是中途多走了一个分岔节点后又重新回到最短路径上，要么是到达最短路径后往回走一个节点再重新走到终点
        //因此这里通过记录节点被访问到的次数来进行剪枝防止超时
        short[] nodeVisitCount = new short[n + 1];
        //对边图进行预处理获得节点连通索引
        List<Integer>[] outMap = new List[n + 1];
        for (int[] edge : edges) {
            List<Integer> outList;
            if (null == outMap[edge[0]]) {
                outList = new ArrayList<>();
                outMap[edge[0]] = outList;
            }
            outMap[edge[0]].add(edge[1]);
            if (null == outMap[edge[1]]) {
                outList = new ArrayList<>();
                outMap[edge[1]] = outList;
            }
            outMap[edge[1]].add(edge[0]);
        }
        //totalTime-总消耗时间，doubleChangeTime-红绿灯从绿-红-绿变化两次消耗的时间
        int totalTime = 0, doubleChangeTime = 2 * change;
        //记录是否已经找到最短路径
        boolean reach = false;
        //BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        ++nodeVisitCount[1];
        while (!queue.isEmpty()) {
            int size = queue.size();
            //用Set去重
            HashSet<Integer> nextNodes = new HashSet<>();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                if (node == n) {
                    //已经找到最短路径
                    reach = true;
                }
                List<Integer> outList = outMap[node];
                for (int nextNode : outList) {
                    if (nodeVisitCount[nextNode] < 2) {
                        //访问次数小于2的节点才能继续被BFS
                        nextNodes.add(nextNode);
                    }
                }
            }
            for (int nextNode : nextNodes) {
                ++nodeVisitCount[nextNode];
                queue.offer(nextNode);
            }
            //计算等待时间waitTime，restTime-总消耗时间对doubleChangeTime的取余，表示经过多次完整的绿-红-绿变化两次之后还剩多少时间
            int waitTime = 0, restTime = totalTime % (doubleChangeTime);
            if (restTime >= change) {
                //如果剩余的时间等于或超过一次change，说明此时所在节点是红灯，需要等待足够的时间转为绿灯才能继续出发
                waitTime = doubleChangeTime - restTime;
            }
            //如果restTime < change，说明所在节点是绿灯，不用等可以直接出发，waitTime是0
            totalTime += (waitTime + time);
            if (nextNodes.contains(n) && reach) {
                //如果已经找到最短路径，并且这一步到达的节点中包含了目标节点n，说明找到次短路径，返回总消耗时间
                return totalTime;
            }
        }
        return totalTime;
    }

    /**
     * 2316【BFS】统计无向图中无法互相到达点对数
     */
    public long countPairs(int n, int[][] edges) {
        Map<Integer, Set<Integer>> graph = new HashMap<>(n);
        for (int[] edge : edges) {
            Set<Integer> nei = graph.getOrDefault(edge[0], new HashSet<>());
            nei.add(edge[1]);
            graph.put(edge[0], nei);
            nei = graph.getOrDefault(edge[1], new HashSet<>());
            nei.add(edge[0]);
            graph.put(edge[1], nei);
        }
        boolean[] visited = new boolean[n];
        List<Integer> groupSizes = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            int groupSize = 1;
            Queue<Integer> q = new LinkedList<>();
            q.offer(i);
            visited[i] = true;
            while (!q.isEmpty()) {
                int l = q.size();
                while (l > 0) {
                    int node = q.poll();
                    Set<Integer> nei = graph.get(node);
                    if (null != nei) {
                        for (int ne : nei) {
                            if (!visited[ne]) {
                                ++groupSize;
                                q.offer(ne);
                                visited[ne] = true;
                            }
                        }
                    }
                    --l;
                }
            }
            groupSizes.add(groupSize);
        }
        long answer = 0;
        int sumOfVisited = 0;
        for (int gs : groupSizes) {
            answer += (long) gs * (n - gs - sumOfVisited);
            sumOfVisited += gs;
        }
        return answer;
    }

    /**
     * 2360【BFS】图中的最长环
     */
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int m = 1;
        int[][] marks = new int[n][2]; //mark, seq
        boolean[] visited = new boolean[n];
        int curr = 0;
        int answer = -1;
        Queue<int[]> queue = new LinkedList<>();
        visited[curr] = true;
        queue.offer(new int[]{0, 1}); //node, seq
        marks[0] = new int[]{m, 1};
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int next = edges[state[0]];
            boolean hasNext = false;
            if (next >= 0) {
                if (marks[next][0] == m) { //找到一个环
                    answer = Math.max(answer, state[1] - marks[next][1] + 1);
                } else if (!visited[next]) {
                    int seq = state[1] + 1;
                    marks[next] = new int[]{m, seq};
                    queue.offer(new int[]{next, seq});
                    visited[next] = true;
                    hasNext = true;
                }
            }
            if (!hasNext) {
                m++; //标记下一个环
                while (curr < n && visited[curr]) {
                    ++curr;
                }
                if (curr < n) {
                    int seq = 1;
                    marks[curr] = new int[]{m, seq};
                    queue.offer(new int[]{curr, seq});
                    visited[curr] = true;
                }
            }
        }
        return answer;
    }

    /**
     * 2415【BFS】反转二叉树的奇数层
     */
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int level = 1;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            TreeNode[] layer = new TreeNode[len];
            TreeNode[] children = new TreeNode[len * 2];
            TreeNode[] subChildren = new TreeNode[len * 4];
            for (int i = 0; i < len; ++i) {
                layer[i] = queue.poll();
                children[2 * i] = layer[i].left;
                children[2 * i + 1] = layer[i].right;
                if (null != layer[i].left) {
                    subChildren[4 * i] = layer[i].left.left;
                    subChildren[4 * i + 1] = layer[i].left.right;
                }
                if (null != layer[i].right) {
                    subChildren[4 * i + 2] = layer[i].right.left;
                    subChildren[4 * i + 3] = layer[i].right.right;
                }
            }
            if ((level & 1) == 1) {
                if (null != children[0]) {
                    //reverse children
                    int l = 0, r = children.length - 1;
                    TreeNode temp;
                    while (l < r) {
                        temp = children[l];
                        children[l] = children[r];
                        children[r] = temp;
                        ++l;
                        --r;
                    }
                    //reconstruct connections
                    for (int i = 0; i < len; ++i) {
                        layer[i].left = children[2 * i];
                        layer[i].right = children[2 * i + 1];
                        children[2 * i].left = subChildren[4 * i];
                        children[2 * i].right = subChildren[4 * i + 1];
                        children[2 * i + 1].left = subChildren[4 * i + 2];
                        children[2 * i + 1].right = subChildren[4 * i + 3];
                    }
                }
            }
            if (null != children[0]) {
                for (int i = 0; i < children.length; ++i) {
                    queue.offer(children[i]);
                }
            }
            ++level;
        }
        return root;
    }

    /**
     * 2596【BFS】检查骑士巡视方案
     */
    public boolean checkValidGrid(int[][] grid) {
        int[][] dirs = new int[][]{{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};
        int r = 0, c = 0, step = 0, n = grid.length, nn = n * n;
        while (step < nn) {
            if (grid[r][c] == -1) break;
            if (grid[r][c] != step) break;
            grid[r][c] = -1;
            for (int i = 0; i < 8; ++i) {
                int[] d = dirs[i];
                int rn = r + d[0];
                int cn = c + d[1];
                if (0 <= rn && rn < n && 0 <= cn && cn < n && grid[rn][cn] > 0) {
                    if (grid[rn][cn] == step + 1) {
                        r = rn;
                        c = cn;
                        ++step;
                        break;
                    }
                }
            }
        }
        return step == nn - 1;
    }

    /**
     * 2612[BFS+有序集合]最少翻转操作数
     * 题解参考：https://leetcode.cn/problems/minimum-reverse-operations/solutions/2204092/liang-chong-zuo-fa-ping-heng-shu-bing-ch-vr0z/?envType=daily-question&envId=2025-03-20
     */
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        Set<Integer> banSet = new HashSet<>(banned.length);
        for (int ban : banned) {
            banSet.add(ban);
        }
        TreeSet<Integer>[] unvisited = new TreeSet[]{new TreeSet<>(), new TreeSet<>()};
        for (int i = 0; i < n; ++i) {
            if (!banSet.contains(i)) {
                unvisited[i % 2].add(i);
            }
        }
        unvisited[p % 2].remove(p);
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        answer[p] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(p);
        while (!queue.isEmpty()) {
            Integer x = queue.poll();
            int l = Math.max(x - k + 1, k - x - 1);
            int r = Math.min(x + k - 1, 2 * n - k - x - 1);
            for (Iterator<Integer> subSetIterator = unvisited[l % 2].tailSet(l).iterator(); subSetIterator.hasNext(); subSetIterator.remove()) { //[l,r]范围内对应的未访问的下标
                Integer j = subSetIterator.next();
                if (j > r) break;
                answer[j] = answer[x] + 1;
                queue.offer(j);
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        BfsSolution solution = new BfsSolution();
        Assert.isTrue(4 == solution.longestCycle(new int[]{1,2,0,4,5,6,3,8,9,7}));
        Assert.isTrue(-1 == solution.longestCycle(new int[]{-1,4,-1,2,0,4}));
        Assert.isTrue(3 == solution.longestCycle(new int[]{3,3,4,2,3}));
//        Assert.isTrue("[3,9,20,null,null,15,7]".equals(solution.buildTree(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3}).serialize()));
//        Assert.isTrue("[1,2]".equals(solution.buildTree(new int[]{2,1}, new int[]{2,1}).serialize()));
    }
}
